#ifndef STX_ALGORITHM_IS_PERMUTATION_HPP
#define STX_ALGORITHM_IS_PERMUTATION_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
inline bool
is_permutation(
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2,
    BinaryPredicate pred)
{
    // shorten sequences as much as possible by lopping of any equal parts
    for (; first1 != last1; ++first1, ++first2) {
        if (!pred(*first1, *first2)) {
            goto not_done;
        }
    }
    return true;
not_done:
    // first1 != last1 && *first1 != *first2
    typedef typename std::iterator_traits<ForwardIterator1>::difference_type Diff;
    Diff l1 = stx::distance(first1, last1);
    if (l1 == Diff(1)) {
        return false;
    }
    ForwardIterator2 last2 = stx::next(first2, l1);
    // For each element in [f1, l1) see if there are the same number of
    //    equal elements in [f2, l2)
    for (ForwardIterator1 i = first1; i != last1; ++i) {
        // Have we already counted the number of *i in [f1, l1)?
        for (ForwardIterator1 j = first1; j != i; ++j) {
            if (pred(*j, *i)) {
                goto next_iter;
            }
        }
        {
            // Count number of *i in [f2, l2)
            Diff c2 = 0;
            for (ForwardIterator2 j = first2; j != last2; ++j) {
                if (pred(*i, *j)) {
                    ++c2;
                }
            }
            if (c2 == 0) {
                return false;
            }
            // Count number of *i in [i, l1) (we can start with 1)
            Diff c1 = 1;
            for (ForwardIterator1 j = stx::next(i); j != last1; ++j) {
                if (pred(*i, *j)) {
                    ++c1;
                }
            }
            if (c1 != c2) {
                return false;
            }
        }
next_iter:;
    }
    return true;
}

template<class ForwardIterator1, class ForwardIterator2>
inline bool
is_permutation(
    ForwardIterator1 first1,
    ForwardIterator1 last1,
    ForwardIterator2 first2)
{
    typedef typename std::iterator_traits<ForwardIterator1>::value_type v1;
    typedef typename std::iterator_traits<ForwardIterator2>::value_type v2;
    return stx::is_permutation(first1, last1, first2, stx::equal_to<v1, v2>());
}

} // namespace stx

#endif // STX_ALGORITHM_IS_PERMUTATION_HPP
